В древние века землю населяли две
команды пиратов: Буканеры и Бербэри. Число пиратов в командах не было
фиксированным, иногда противники нападали друг на друга и превращали пленных в
членов своей команды. Однажды в пиратской земле появился волшебник, который
начал совершать переход пиратов из одной команды в другую по собственному
желанию. Для этого были использованы необходимые заклинания. Процесс смены
команды назывался мутацией.
Всего имеется n пиратов, каждый из которых имеет уникальный
идентификационный номер id от 0 до n – 1. Великий маг может видоизменять
набор пиратов с последовательными идентификационными номерами на другой.
Пусть на земле имеются 100
пиратов, и все они являются Бербэри пиратами. Маг совершает заклинание, которое
изменяет пиратов с id от 10 до 33 на Буканеров. Теперь во всей земле имеются 24
Буканеров и 76 Бербэри пиратов.
Волшебник начал слишком быстро
выполнять заклинания. Однажды Богу не понравилось это. Бог был милостив к
Буканерам и спросил волшебника "Скажи мне, сколько пиратов с индексами от
2 до 30 являются Буканерами?". Теперь маг был озадачен, поскольку он был
эффективен только в заклинаниях, но не в подсчете :-).
Будучи достаточно умным, маг
захватил умного человека из планеты Земля. К сожалению, это были Вы! Теперь Вы
должны ответить на вопросы Богов.
Вход. Первая
строка содержит количество тестов t.
Структура каждого теста следующая:
Первая
часть входных данных описывает пиратскую землю. Она содержит до n (1 ≤ n ≤ 1024000) пиратов. Каждый пират принадлежит или команде
Буканеров или Бербэри. Буканеры пираты обозначаются '1' (ОДИН), а Бербэри
пираты обозначаются '0' (НОЛЬ). Вам следует построить строку пиратов из входных
данных. Каждый тест начинается числом m
(m ≤ 100), за которым следует m пар строк. В каждой паре строк (будем
называть ее набором), первая содержит целое число t (t ≤ 200), а
вторая – непустую строку пиратов (состоящую из 0 и 1, 0 - Бербэри, 1 -
Буканеры, ее длина не более 50). Совершите конкатенацию этой строки с собой t раз. Теперь сконкатенируйте
результирующие m наборов строк и
получите строку – описание пиратов. Финальное объединение строк описывает
пиратов начиная с индекса 0 и до конца (индекс n – 1 для n-го пирата).
Следующая
часть входных данных содержит вопросы. Первая строка єтой части содержит
количество вопросов q. Каждая из
следующих q (1 ≤ q ≤ 1000) строк содержит один
вопрос. Каждый вопрос начинается одной из букв F, E, I или S,
за которой следуют два целых числа – индексы a и b. Значение
этих запросов следующее:
F
a b означает мутировать пиратов с
индексами от a до b в Буканер пиратов.
E
a b означает мутировать пиратов с
индексами от a до b в Бербэри пиратов.
I
a b означает мутировать пиратов с
индексами от a до b в инвертированных пиратов.
S
a b означает "вопрос Бога",
Бог задает вопрос: "Скажи мне сколько Буканеров находится среди пиратов с
индексами от a до b?"
(a ≤ b, 0 ≤ a < n, 0 ≤ b < n, границы
диапазона включительно)
Выход. Для каждого теста вывести его
номер. Для каждого вопроса Бога вывести в отдельной строке его номер, двоеточие
(:), пробел и ответ на вопрос.
Пример входа
2
2
5
10
2
1000
5
F 0 17
I 0 5
S 1 10
E 4 9
S 2 10
3
3
1
4
0
2
0
2
I 0 2
S 0 8
Пример выхода
Case 1:
Q1: 5
Q2: 1
Case 2:
Q1: 0
дерево отрезков
На дереве отрезков следует
промоделировать четыре множественные операции:
·
Установка 1 – SET
·
Установка 0 – CLEAR
·
Инвертирование – FLIP
·
Запрос суммы
Ни одна из операций модификаций
на отрезке не имеет параметров, поэтому в вершинах дерева отрезков достаточно
содержать только сумму (summa) и тип (type) отложенной операции.
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX 1024010
#define NORMAL 0
#define SET 1
#define CLEAR 2
#define FLIP 3
using namespace
std;
int i, j, k, t, n, m, tests, cs, q, q1;
int l, r;
struct node
{
int summa,
type;
};
vector<node>
SegTree;
char ch, s[100];
int a[MAX];
void build(int
*a, int Vertex, int
Left, int Right)
{
SegTree[Vertex].type = NORMAL;
if (Left ==
Right)
SegTree[Vertex].summa = a[Left];
else
{
int Middle
= (Left + Right) / 2;
build (a,2*Vertex, Left, Middle);
build (a,2*Vertex+1, Middle+1, Right);
SegTree[Vertex].summa =
SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;
}
}
int ApplyFlip(int
type)
{
if (type ==
SET) return CLEAR;
if (type ==
CLEAR) return SET;
if (type ==
FLIP) return NORMAL;
return FLIP; // type = NORMAL
}
void Push(int
Vertex, int LeftPos, int
Middle, int RightPos)
{
if
(SegTree[Vertex].type == SET)
{
SegTree[2*Vertex].type = SegTree[2*Vertex+1].type
= SegTree[Vertex].type;
SegTree[2*Vertex].summa = Middle - LeftPos
+ 1;
SegTree[2*Vertex+1].summa = RightPos -
Middle;
SegTree[Vertex].type = NORMAL;
} else
if
(SegTree[Vertex].type == CLEAR)
{
SegTree[2*Vertex].type =
SegTree[2*Vertex+1].type = SegTree[Vertex].type;
SegTree[2*Vertex].summa =
SegTree[2*Vertex+1].summa = 0;
SegTree[Vertex].type = NORMAL;
} else
if
(SegTree[Vertex].type == FLIP)
{
SegTree[2*Vertex].type = ApplyFlip(SegTree[2*Vertex].type);
SegTree[2*Vertex+1].type =
ApplyFlip(SegTree[2*Vertex+1].type);
SegTree[2*Vertex].summa = Middle - LeftPos
+ 1 - SegTree[2*Vertex].summa;
SegTree[2*Vertex+1].summa = RightPos -
Middle - SegTree[2*Vertex+1].summa;
SegTree[Vertex].type = NORMAL;
}
}
void Set(int
Vertex, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left >
Right) return;
if ((LeftPos
== Left) && (RightPos == Right))
{
SegTree[Vertex].type = SET;
SegTree[Vertex].summa = Right - Left + 1;
return;
}
int Middle =
(LeftPos + RightPos) / 2;
Push(Vertex,LeftPos,Middle,RightPos);
Set(2*Vertex, LeftPos, Middle, Left,
min(Middle,Right));
Set(2*Vertex+1, Middle+1, RightPos,
max(Left,Middle+1), Right);
SegTree[Vertex].summa =
SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;
}
void Clear(int
Vertex, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left >
Right) return;
if ((LeftPos
== Left) && (RightPos == Right))
{
SegTree[Vertex].type = CLEAR;
SegTree[Vertex].summa = 0;
return;
}
int Middle =
(LeftPos + RightPos) / 2;
Push(Vertex,LeftPos,Middle,RightPos);
Clear(2*Vertex, LeftPos, Middle, Left,
min(Middle,Right));
Clear(2*Vertex+1, Middle+1, RightPos,
max(Left,Middle+1), Right);
SegTree[Vertex].summa =
SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;
}
void Flip(int
Vertex, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left >
Right) return;
if ((LeftPos
== Left) && (RightPos == Right))
{
SegTree[Vertex].type =
ApplyFlip(SegTree[Vertex].type);
SegTree[Vertex].summa = Right - Left + 1 -
SegTree[Vertex].summa;
return;
}
int Middle =
(LeftPos + RightPos) / 2;
Push(Vertex,LeftPos,Middle,RightPos);
Flip(2*Vertex, LeftPos, Middle, Left, min(Middle,Right));
Flip(2*Vertex+1, Middle+1, RightPos,
max(Left,Middle+1), Right);
SegTree[Vertex].summa =
SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;
}
int Summa(int
Vertex, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left >
Right) return 0;
if ((LeftPos
== Left) && (RightPos == Right))
return
SegTree[Vertex].summa;
int Middle =
(LeftPos + RightPos) / 2;
Push(Vertex,LeftPos,Middle,RightPos);
return
Summa(2*Vertex, LeftPos, Middle, Left, min(Middle,Right)) +
Summa(2*Vertex+1, Middle+1, RightPos,
max(Left,Middle+1), Right);
}
int main(void)
{
scanf("%d",&tests);
for(cs = 1;
cs <= tests; cs++)
{
scanf("%d",&m);
n = 0;
for(i = 0;
i < m; i++)
{
scanf("%d\n",&t);
gets(s);
for(k =
0; k < t; k++)
for(j =
0; j < strlen(s); j++)
a[n++] = s[j] - '0';
}
SegTree.resize(4*n);
build(a,1,0,n-1);
printf("Case
%d:\n",cs);
scanf("%d\n",&q);
q1 = 1;
for(j = 0;
j < q; j++)
{
scanf("%c
%d %d\n",&ch,&l,&r);
if (ch ==
'F')
Set(1,0,n-1,l,r);
else
if (ch ==
'E')
Clear(1,0,n-1,l,r);
else
if (ch ==
'I')
Flip(1,0,n-1,l,r);
else // ch == 'S'
printf("Q%d:
%d\n",q1++,Summa(1,0,n-1,l,r));
}
}
return 0;
}